package com.wsx.first.d;

import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * Created by wangshunxi on 2022/5/14.
 * e-mail: wsr12240512@163.com
 * phone: 13388071923
 */
public class Main0045 {
    public static void main(String[] args) {
        Main0045 main0045 = new Main0045();
        int[] ints = {2,3,4,2,6,2,5,1};
        main0045.maxInWindows(ints,3);
    }
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //窗口大于数组长度的时候，返回空 fast-template
        if(size <= num.length && size != 0){
            //双向队列
            ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
            //先遍历一个窗口
            for(int i = 0; i < size; i++){
                //去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            //遍历后续数组元素
            for(int i = size; i < num.length; i++){
                //取窗口内的最大值
                res.add(num[dq.peekFirst()]);
                while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
                    //弹出窗口移走后的值
                    dq.pollFirst();
                //加入新的值前，去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            res.add(num[dq.pollFirst()]);
        }
        return res;
    }
}
